/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 最长没有重复的子串
 * 
 * 输入： "abcabcbb" 返回 "abc", which the length is 3. 
 * For "bbbbb" the longest substring is "b", with the length of 1.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月25日
 */
public class LongestSubstringWithoutRepeatingCharacters {

 public int lengthOfLongestSubstring(String s) {
     int result = 0;
        if(s == null){
            return result;
        }
        Map<Character,Integer>  map = new HashMap<>();
        int start = 0;
        char[] chs = s.toCharArray();
        for(int i=0;i<chs.length;i++){
            char ch = chs[i];
           if(map.containsKey(ch) && map.get(ch)>=start){
               start = map.get(ch)+1;
           }
           map.put(ch, i);
           result = Math.max(result, i-start+1);
        }
        return result;
    }
 
     public static void main(String[] args) {
        String str = "pwwkew";
        LongestSubstringWithoutRepeatingCharacters lStr = new LongestSubstringWithoutRepeatingCharacters();
        System.out.println(lStr.lengthOfLongestSubstring(str));
    }
}
